翻訳と辞書
Words near each other
・ Bipalium kewense
・ Bipalium pennsylvanicum
・ Bipan Chandra
・ Bipana Thapa
・ Bipartisan Budget Act of 2013
・ Bipartisan Campaign Reform Act
・ Bipartisan Legal Advisory Group
・ Bipartisan Policy Center
・ Bipartisan Sportsmen's Act of 2014
・ Bipartisan Student Loan Certainty Act of 2013
・ Bipartisanship
・ Bipartite
・ Bipartite (theology)
・ Bipartite dimension
・ Bipartite double cover
Bipartite graph
・ Bipartite half
・ Bipartite matroid
・ Bipartite network projection
・ Bipartite patella
・ Bipartite realization problem
・ Bipartivalva
・ Bipasha
・ Bipasha (film)
・ Bipasha Basu
・ Bipasha Basu filmography
・ Bipasha Hayat
・ Bipectilus
・ Bipectilus gracilirami
・ Bipectilus latirami


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Bipartite graph : ウィキペディア英語版
Bipartite graph

In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint sets U and V (that is, U and V are each independent sets) such that every edge connects a vertex in U to one in V. Vertex set U and V are often denoted as ''partite sets''. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.〔.〕
The two sets U and V may be thought of as a coloring of the graph with two colors: if one colors all nodes in U blue, and all nodes in V green, each edge has endpoints of differing colors, as is required in the graph coloring problem.〔〔.〕 In contrast, such a coloring is impossible in the case of a non-bipartite graph, such as a triangle: after one node is colored blue and another green, the third vertex of the triangle is connected to vertices of both colors, preventing it from being assigned either color.
One often writes G=(U,V,E) to denote a bipartite graph whose partition has the parts U and V, with E denoting the edges of the graph. If a bipartite graph is not connected, it may have more than one bipartition;〔.〕 in this case, the (U,V,E) notation is helpful in specifying one particular bipartition that may be of importance in an application. If |U|=|V|, that is, if the two subsets have equal cardinality, then G is called a ''balanced'' bipartite graph.〔, p. 7.〕 If all vertices on the same side of the bipartition have the same degree, then G is called biregular.
==Examples==
When modelling relations between two different classes of objects, bipartite graphs very often arise naturally. For instance, a graph of football players and clubs, with an edge between a player and a club if the player has played for that club, is a natural example of an ''affiliation network'', a type of bipartite graph used in social network analysis.〔.〕
Another example where bipartite graphs appear naturally is in the (NP-complete) railway optimization problem, in which the input is a schedule of trains and their stops, and the goal is to find a set of train stations as small as possible such that every train visits at least one of the chosen stations. This problem can be modeled as a dominating set problem in a bipartite graph that has a vertex for each train and each station and an edge for
each pair of a station and a train that stops at that station.
A third example is in the academic field of numismatics. Ancient coins are made using two positive impressions of the design (the obverse and reverse). The charts numismatists produce to represent the production of coins are bipartite graphs.
More abstract examples include the following:
* Every tree is bipartite.〔
* Cycle graphs with an even number of vertices are bipartite.〔
* Every planar graph whose faces all have even length is bipartite.〔. This result has sometimes been called the "two color theorem"; Soifer credits it to a famous 1879 paper of Alfred Kempe containing a false proof of the four color theorem.〕 Special cases of this are grid graphs and squaregraphs, in which every inner face consists of 4 edges and every inner vertex has four or more neighbors.〔.〕
* The complete bipartite graph on ''m'' and ''n'' vertices, denoted by ''Kn,m'' is the bipartite graph ''G = (U, V, E)'', where ''U'' and ''V'' are disjoint sets of size ''m'' and ''n'', respectively, and ''E'' connects every vertex in ''U'' with all vertices in ''V''. It follows that ''Km,n'' has ''mn'' edges.〔, p. 11.〕 Closely related to the complete bipartite graphs are the crown graphs, formed from complete bipartite graphs by removing the edges of a perfect matching.〔.〕
* Hypercube graphs, partial cubes, and median graphs are bipartite. In these graphs, the vertices may be labeled by bitvectors, in such a way that two vertices are adjacent if and only if the corresponding bitvectors differ in a single position. A bipartition may be formed by separating the vertices whose bitvectors have an even number of ones from the vertices with an odd number of ones. Trees and squaregraphs form examples of median graphs, and every median graph is a partial cube.〔. See especially Chapter 5, "Partial Cubes", pp. 127–181.〕

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Bipartite graph」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.